This invention relates to a method and apparatus for digital addition, and in particular, to a method and apparatus for structuring a carry-look-ahead adder.
The carry-look-ahead adder (CLA) is a key element in digital computers. It is an integral element in the efficient implementation of high-speed arithmetic units and is used in most arithmetic operations, including addition, subtraction, multiplication, division, and square root. The adder function requires complex circuitry for fast implementation, and can be a bottleneck to speed. Thus, performance improvements in the carry-look-ahead adder directly affect computer performance in computationally intensive applications.
In a conventional M-bit carry-look-adder, a pair of M-bit input numbers are used to obtain the associated generate and propagate values. The conventional carry-look-ahead adder implementation then requires 2ceiling[log(M)]-1 stages for the calculation of the carry-in for each column using the generate and propagate values. For example, with a fan-in limit of four, four bits of input data require one stage, sixteen bits require three stages, and sixty-four bits require five stages. In the final step, the carry-ins are combined with the two M-bit inputs to produce the sum.
The computational speed of the adder is proportional to log(M). Since the number of stages required in a given computation directly affects the overall speed of the arithmetic operation, the implementation of a CLA with fewer stages is desirable. It is true that the number of gate delays ill each CLA stage is implementation dependent. Nevertheless, as demonstrated, the number of stages in the CLA increases with the log of the number of input bits, thereby increasing the net delay through the adder. In other words, a large number of input bits materially affects CLA speed and, as a result, processor speed. Therefore, a reduction in the number of stages in a carry-look-ahead adder would materially improve the speed of a given arithmetic unit in a digital computer.